package org.basis.algorithm.promote;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 单调栈
 * 在数组中想找到一个数，左边和右边比这个数小、且离这个数最近的位置。
 * 如果对每一个数都想求这样的信息，能不能整体代价达到O(N)?需要使用到单调栈结构 单调栈结构的原理和实现
 *
 * @author Mr_wenpan@163.com 2022/01/10 21:33
 */
public class MonotonousStack {

    public static void main(String[] args) {
        final int size = 10;
        final int max = 20;
        final int testTimes = 2000000;
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = getRandomArrayNoRepeat(size);
            int[] arr2 = getRandomArray(size, max);
            if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
                System.out.println("Oops!");
                printArray(arr1);
                break;
            }
            if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
                System.out.println("Oops!");
                printArray(arr2);
                break;
            }
        }
    }

    /**
     * 对数组中的每个位置都找出他左边离他最近且比他小的位置和右边离他最近且比他小的位置的下标
     * 这里arr数组需要满足无重复值，如果是有重复值的话，那么栈里元素面应该用LinkedList类型而不是integer(编码上会复杂一些)
     */
    public static int[][] getNearLessNoRepeat(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        // 返回结果，这里返回的是左边比i位置的数大的数（且距离最近的）的下标，右边比i位置的数大的数（且距离最近的）的下标
        int[][] res = new int[arr.length][2];
        // 一个从栈底到栈顶单调递增的栈
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            // 栈不为空且栈顶元素大于当前元素
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                // 注意这里pop的是下标
                Integer popIndex = stack.pop();
                // 左边比popIndex位置上的数小的下标就是popIndex压着的那个(如果栈为空，那么就是没有，这里用-1表示)
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                res[popIndex][0] = leftLessIndex;
                // 右边比popIndex位置上的数大的就是让popIndex弹出的那个（也就是i位置）
                res[popIndex][1] = i;
            }
            // 将i位置的下标压栈
            stack.push(i);
        }

        // 如果上面的遍历跑完了，但是栈中仍然还有数据（此时栈中的数据从栈底到栈顶一定是一个严格递增的了）
        while (!stack.isEmpty()) {
            Integer popIndex = stack.pop();
            // 左边比popIndex位置的数小的就是他压着的那个（栈不空的情况下）
            res[popIndex][0] = stack.isEmpty() ? -1 : stack.peek();
            // 此时已经是严格递增的栈了，所以不存在右边比popIndex位置小的数了，所以用-1表示
            res[popIndex][1] = -1;
        }

        return res;
    }

    /**
     * arr中有重复值的解法
     */
    public static int[][] getNearLess(int[] arr) {
        int[][] res = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
                List<Integer> popIs = stack.pop();
                // 取位于下面位置的列表中，最晚加入的那个
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
                        stack.peek().size() - 1);
                for (Integer popi : popIs) {
                    res[popi][0] = leftLessIndex;
                    res[popi][1] = i;
                }
            }
            if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
                stack.peek().add(i);
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while (!stack.isEmpty()) {
            List<Integer> popIs = stack.pop();
            // 取位于下面位置的列表中，最晚加入的那个
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
                    stack.peek().size() - 1);
            for (Integer popi : popIs) {
                res[popi][0] = leftLessIndex;
                res[popi][1] = -1;
            }
        }
        return res;
    }

    // ===================>>>>>>>>>>>>>>>>下面都是一些测试方法

    // for test
    public static int[] getRandomArrayNoRepeat(int size) {
        int[] arr = new int[(int) (Math.random() * size) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        for (int i = 0; i < arr.length; i++) {
            int swapIndex = (int) (Math.random() * arr.length);
            int tmp = arr[swapIndex];
            arr[swapIndex] = arr[i];
            arr[i] = tmp;
        }
        return arr;
    }

    // for test
    public static int[] getRandomArray(int size, int max) {
        int[] arr = new int[(int) (Math.random() * size) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
        }
        return arr;
    }

    /**
     * 暴力解法，for test 对数器
     */
    public static int[][] rightWay(int[] arr) {
        int[][] res = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++) {
            int leftLessIndex = -1;
            int rightLessIndex = -1;
            int cur = i - 1;
            while (cur >= 0) {
                if (arr[cur] < arr[i]) {
                    leftLessIndex = cur;
                    break;
                }
                cur--;
            }
            cur = i + 1;
            while (cur < arr.length) {
                if (arr[cur] < arr[i]) {
                    rightLessIndex = cur;
                    break;
                }
                cur++;
            }
            res[i][0] = leftLessIndex;
            res[i][1] = rightLessIndex;
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[][] res1, int[][] res2) {
        if (res1.length != res2.length) {
            return false;
        }
        for (int i = 0; i < res1.length; i++) {
            if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
                return false;
            }
        }

        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}
